COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002				NOTES ON A REAL COMPILER
C00012 00003			BINDING AND INTERCOMMUNICATION BETWEEN
C00031 00004				SYSTEMS ORGANIZATION
C00053 00005				NUMBERS IN LISP
C00057 00006			STORAGE STRUCTURES AND EFFICIENCY
C00082 ENDMK
C⊗;
			NOTES ON A REAL COMPILER

	The major failing of the `test compiler' is its total lack of
interest  in variables.  This is  a  non-trivial problem  which every
compiler must  face.    You  have seen  examples  of  plausible  code
generation for simple LISP functions, in particular:

			j[x;y] = f[g[x];h[y]]

The crucial (not crutial) point is how to generate code which `knows'
where on  the stack we can find the value  of a (local) variable when
we execute that code.  What  we shall do is simulate the behavior  of
the runtime  stack while  we are  compiling the  code.   The compiler
cannot  know what the values of the  variables will be at runtime but
we claim that it should know where to find the values.  We will carry
this information through the  compiler in a manner reminiscent of the
`dotted-pair' symbol table of the first version of eval.  Instead  of
posting the current values  in the stack, the compiler  will post the
positions  of the variables relative  to the top of  the stack at the
time we enter  the function.   The variable,  vpr, in London's  paper
(from now on called LP) contains this information.  That is if we are
to compile  a function with λ-variables, [x;y;z] then vpr would begin
with:

			((X . 1), (Y . 2), (Z .3) ...

We also set the offset,  called M, to minus the number  of args added
to vpr. (In this  case -3).  Now if we come across a reference say to
Y while compiling code, we  use assoc [Y ;  vpr] to retrieve 2.   The
offset plus this retrieved value gives  us the relative position of Y
in  the stack.   I. e.,  -3 +  2 = -1.   Thus  to refer  to the stack
location of Y  we could  use (....-1 ,  P).  What  happens as we  add
elements to  the stack? (Or to  be more precise...what  happens as we
generate code which when  executed will add  elements to the  stack.)
Clearly we must modify the  offset.  If we add one  element, we would
set  M to -4.   Then to reference  Y now use  -4 + 2  = -2.   I. e. a
reference to Y is of the form:

			( ......-2 P).

But that's right.  Y  is now further down in the run time  stack.  So
to  complete the analogy, the  `symbol table' is really  defined by M
plus the  current  vpr.    The other  alternative  of  modifying  the
cdr-parts of the entries in the vpr every time we modify the stack is
gross as hell!!
	How do  we make modifications  to the top  of the stack?   We
push new  elements when we are compiling  the arguments to a function
call.  The function  in the LP  compiler which compiles the  argument
list is called complis:

			complis [u;m;vpr] =
				[null [u] → NIL
				T → append [compexp [car [u]; m; vpr];
						((PUSH P 1));
						complis [cdr [u]; m-1; vpr]]]
Notice  that   it  compiles  the   arguments  from  left   to  right,
interspursing  them with (PUSH P  1) and recurring with  a new offset
reflecting the push.
	Here's a brief description of the parts of the LP compiler: 
comp: fn is  the name of  the function to be  compiled.  vars  is the
list of lambda variables.  exp is the lambda-body.
prup:  vars is  a  lambda list,  n  is an  integer.   prup  builds  a
variable-pair list.
mkpush:  generates a sequence of PUSH instructions.
compexp: this  function does most  of the work.   It is  analogous to
eval.
The code for constants is generated by lines [1], [2], and [6].
line [3] generates code for a reference to a variable.
line  [4]  handles  the generation  of  code  for  optimized  Boolean
expressions (the compiler's analog to `more efficient ands and ors').
line [7] is  used for compiling code for  a call on a function.   The
body of line  [7] compiles the argument list with complis, which will
leave the arguments in the stack; loadac loads the  appropriate Ac's.
and then we generate the SUB  to sync the stack, and finally generate
a call on the function.
line [8] you can ignore unless you're really interested.  It compiles
an explicit call on a lambda expression.  The arguments are found and
manipulated directly in the stack rather than being moves to the Acs.
comcond: this compiles the body of conditional expressions.  u is the
p  (sub)i - e (sub)i  list will be  bound to a  generated symbol name
(gensym); M and vpr are as always.  Notice that there is more  than a
passing similarity between comcond and evcond.
combool  and compandor:  are  compile functions  to  try to  generate
reasonable codes for predicates in comcond.
Here is a  transliteration of the  LP compiler's main  functions, and
following  that a specialization  of the  compiler to thhe  subset of
LISP in problem 2.  Then following that a sample compilation of:

  rev = λ[[x;y][null [x] → y; T → rev [cdr [x]; cons [car [x];y]]]]


comp [fn;vars;exp]=
	prog[[n]
	    n ← length [vars];
	return [append [list [LAP;fn;SUBR]];
			mkpush [n;1];
			conpexp [exp; -n; prup [vars;1]]
			list [list [SUB;P;list [C;O;O;n;n]]]
			((POPJ P) NIL) ]]]

prup [vars;n] =
	[null [vars] → NIL
	T → cons [cons [car [vars]; n]; prup [cdr [vars];n+1]]]

mkpush [n;m] =
	[lessp [n;m] → NIL
	T → cons [list [PUSH;p;m]; mkpush [n;m+1]]]



compexp [exp;m;vpr] =
	[null [exp] → ((MOVEI 1 0));
	or [eq [exp;T]; numberp [exp]] → list [list [MOVEI;1;list [QUOTE; exp]]];
	atom [exp] → list [list [MOVE;1;m + cdr [assoc [exp;vpr]]; P]];
	(line 4)
	eq [car [exp]; COND] → comcond [cdr [esp]; m; gensym [ ]; vpr];
	eq [car [exp]; QUOTE] → list [list [MOVEI;1;exp]];
	eq [atom [car [exp]] → λ[[n][append [complis [cdr [exp];m;vpr]
				 	     loadac [1-n;1];
					*    list [list [SUB;P;list [C;O;O;n;n]]
						list [list [CALL;n;
							list [E; car [exp]]]]]
				[length [cdr [exp]]]

line 8

* This is sufficiently mysterious to warrant explanation.  The λ-mess is a 
  function of one argument, n.  It is called, binding n to length [cdr [exp]];

comcond [u;m; ;vpr]=
	[null [u] → list[ ];
	T → λ[[  ] append [combool [caar [u];m;  ;NIL;vpr]
			   compexp [cadar [u];m;vpr]:
			   list [list [JRST; ];  ]
			   comcond [cdr [u];m;  ;vpr]]]
		gensym [ ]]



N.B. same trickery used here as in compexp:   is bound to value of gensym [ ].
		BINDING AND INTERCOMMUNICATION BETWEEN
		  COMPILED AND INTERPRETED FUNCTIONS

               Global Variables and Functional Arguments

	The models of compilation which we have sketched so far store
their  lambda  variables  in  the  stack,  P.   References  to  those
variables in  the body of  the lambda  expression are  made to  those
stack entries.  This scheme suffices  only for lambda or prog (local)
variables.   We have said that labmda expressions may refer to global
or free  variables.  The  lookup mechanism  simply finds the  current
binding of  that global in the  symbol table.  Notice that  this is a
different strategy than the global lookup of Algol.  In Algol, when a
procedurerefers to a global we take the  binding which was current at
the  point of definition  of the procedure.   The  LISP rmechanism is
called dynamic binding.   It corrresponds to physically  substituting
the body  of the definition  of the  function wherever it  is called.
Its model  of implementation is simpler than that required for Algol.
We don't need the static chain for this case of  global lookup.  Thus
interpreted expressions encounter  no problems when faced with global
variables.  There are potential  difficulties for compiled code.   If
all we store  of the stack in a  compiled sunction is the value  of a
variable  then another  program which  expects  to use  that variable
globally will have no way of  finding that stored value.  One  scheme
is to store  pairs on the stack:  name and value (LISP  1.85) then we
can  search the stack for  the latest binding.  It  works.  With this
scheme we  can dispense  with the  VALUE cell.  Actually this  scheme
isn't  all that bad.   The  compiler can still  `know' where  all the
local variables  are on  the stack  and  can be  a bit  clever  about
searching for  the  globals.   Notice this  is the  old symbol  table
mechanism  (a-list)  again.   LISP  1.85 was  designed  for  a paging
machine (XDS 940) and a  few unpleasant features crept in because  of
this.   (However, on  the positive  side some  nice coding  tricks to
minimize page references also arose.)
	The solution proposed  by the LISP 1.6  implementation called
shallow  binding, allows  the compiled  code  to directly  access the
VALUE-cell in the symbol table.  There is an artifcat in the compiler
(and  assmbler) called  SPECIAL.    Variables which  are  to be  used
globally  are declared special variables.   When a  variable say X is
declared special the compiler will emit a reference to X as (MOVE ACi
(SPECIAL X)) or MOVEM  ACi (SPECIAL X)) rather than the corresponding
reference to a location on the  stack.  When the LISP assembler  sees
the indicator SPECIAL, it will search the  symbol table for the VALUE
cell of X and  assemble a reference to that cell.  Since the location
of the value  cell does not  change, we can  always find the  current
binding posted  in the  cdr-part of  that cell.  Notice too  that any
interpreted function  can also sample the VALUE cell so global values
can be passed between compiled and interpreted functions.  The values
of local variables are still posted on the stack.
	We have not yet  discussed the mechanism which will  allow us
to  pass back and  forth between compiled  and interpreted functions.
That is,  compiled can  call interpreted  and conversely.   First  we
require that the  calling conventions for both kinds  of functions be
isomorphic.
	When an interpreted function calls  a compiled (or primitive)
function, eval will  look for the indicator,  SUBR; then retrieve the
machine address of the code and enter via a PUSHJ.Mumble, no problem.
	Compiled functions  call other functions  via the (CALL  n (E
fn))  artifact.  The Call  opcode is actually  an illegal instruction
which is trapped to a submonitor inside eval.  This  submonitor looks
down the  property list  of the  atom, fn,  for a  function indicator
(SUBR,  EXPR,  etc).  The  function is  called  and  control  is then
returned to  the address  immediately following  the CALL.   In  many
cases this Call can be replaced  by a (PUSHJ P fn), but not always as
we will see next.

		    Functional Arguments

A functional argument is  a variable (lambda or prog  variable) whose
value  will be a  function (a name  or lambda-expression).   You have
already seen a very simple case of this:

	λ[[x;y] x[y]] [CAR; (A B)] or
	   ((LAMBDA (X Y) (X Y)) (QUOTE CAR) (QUOTE (A B)))

The variable, x, is a functional argument.  If you did go through the
execution of this  example you found that `the right thing happened'.
That is, we finally ended up applying he car function to the list, (A
B).  Notice that we assigned a value to the functional argument using
QUOTE.     This  is  not  by  accident.  Recall  that  LISP  performs
call-by-value.   What  we want  to pass  to the  body  of the  lambda
expression is not the value of car but the name of the function.  How
do we stop  evaluation of an  argument??   We quote it!!   The  world
isn't quite this simple.  The quote operator does not suffice for all
applications of functional arguments.  Consider the following strange
function.

	tester = λ[[ ;fn] [null[ ] → NIL;atom[ ] → fn];
		 T → tester [car[ ];`λ[[]tester[cdr[ ];fn]]']]
(notice, we are using `...' to signify quoting.)

and a call  on tester: tester  [(A(B) (C));`λ[[] foo [A]]']  thus: is
bound to be (A (B) (C)), fn is bound to `λ[[]foo[A]]', p (sub)1 and p
(sub)2 are false and thus we take the `otherwise' branch.   We rebind
fn  to `λ[[]tester[cdr[  ]'fn]' and  lose big.   When  we attempt  to
evaluate cdr  [ ] we get the wrong !  The environment at the point of
call in e (sub)3 should have been associated with  fn when we rebound
fn. That is, we must  associate the symbol table which was current at
the point of call with the functional argument.  This solution  might
seem a bit  drastic, but it is  easy to generate counter  examples to
less sophisticated implementations.
	What does  this say  about functions?   We  already say  that
functions are  parametric values; to that we  add: functions are also
tied to the environment  in which they  were created; they cannot  be
evaluated in vacuo.   (Notice that the problem goes  away if we don't
have   global  variables.)   The  device   LISP  uses   to  associate
environments with functions is called FUNARG.  Instead of designating
a `value' which is to be  used as a function by the QUOTE operator we
use the indicator, FUNCTION.  Thus:
 
	function [λ[[] tester[cdr [ ]; fn]]] or
	(FUNCTION (LAMBDA ()(TESTER (CDR L FN)))

When eval sees  the indicator (FUNCTION  fn) it returns as  value the
list:

	(FUNARG fn current-symbol table).

When eval (or actually  apply) sees (FUNARG fn st), that  is, when we
are calling gn, we use theol table, for accessing global variables.
	It should be apparent that (QUOTE fn)  and (FUNCTION fn) will
have the same effect if fn has no global (or free variables).
	This seems to be  a lot of work simply to  allow a moderately
obscure  construct to  appear in  the  language.   This is  not true.
Constructs like  functional  arguments  appear  in  most  programming
languages  under different  names (think  about it)  but in  LISP the
problem and the solution appear with exceptional clarity.  Also, in a
more sophisticated  vein, functional  arguments may  be exploited  to
describe  very general  kinds  of control  structures  in programming
languages.   Co-routines,  back-tracking,  and  multi-processing  are
modeled very naturally as applications of functional arguments.  What
does this say about  the CALL mechanism n the compiler?  It says that
the calling  mechanism  for  a  functional argument  must  always  be
trapped the submonitor and decoded.  We cannot replace that call with
a  PUSHJ to some machine  language code for  the function because the
function referred to can chage.  We actually use  a CALLF instruction
to designate a call on a functional argument.
	
		Tracing and debugging in LISP

	When can the  CALL instruction be  replaced by a PUSHJ?   The
PUSHJ  instruction  is  used to  call  a  machine language  function.
Obviously  if  we  are  calling  an  interpreted  function,(  it  has
indicator EXPR  of FEXPR) PUSHJ  is the wrong thing  to do.   In this
case  we must pass  control to  eval, evaluate the  function with the
appropriate arguments,   return the value  in AC1 and finally  return
control to the instruction following the CALL.  If the function being
called is a  machine language  routine (indicator is  SUBR or  FSUBR)
then  we  could  replace   the  CALL  with  a  PUSHJ.     This  would
`short-circuit'  the call on  the submonitor  and the calling  of the
function could be  done more quickly.   There  are many occasions  in
which we do not wish to make this replacement, however.
	Assume for  the  moment that  I am  mortal and  that my  LISP
program  has some  bugs.   Crutial  pieces of  information  about the
behavior of the program are: which functions are being  entered, what
are  the actual  parameters, and what are the  values being returned.
Assume that  we wish to monitor the behavior of the function, FOO. We
will hide the  real definition of FOO  on another symbol table  entry
(using gengym[])  and redefine FOO such  that, when it  is called, it
will:

	1.  print the values of the current actual parameters.
	2.  use  apply  to call  the real  definion of  FOO with  the
	    current parameters.
	3.  print the value of the call on FOO.
	4.  return control to the calling program.

This device is called tracing.
	Since  FOO  may  be  recursive  we   should  also  give  some
indication of the  depth of recursion being executed.  Now every call
on FOO will give us  the pertinent statistics.  Interpreted calls  on
FOO will  go through eval, and  if (CALL...FOO) is being  used in the
compiled  code  the  submonitor  can  pass  control  to  the  tracing
mechanism; but if the CALL is replaced by a PUSHJ, the control passes
directly to the machine language code for FOO and we cannot intercept
the call.
	On most implementations  of LISP the PUSHJ-Call  mechanism is
under  the  control   of  the  programmer.    After  the  program  is
sufficiently debugged,  replace  the  CALL  with the  PUSHJ  and  the
programs will  execute faster.   But  be warned  that this  action is
irreversible; one the CALLs have been overwritten it's tough beans!!
	A variant of this tracing scheme can  be used to monitor SETs
and  SETQs in  interpreted progs.   Since calls  on SET and  SETQ are
interpreted (by eval  and Co.),  we can modify  their definitions  to
print the  name of the  variable and the  new assignment, do  it, and
return.  (question: can you see why this perhaps won't (or shouldn't)
work for compiled code?) Much more sophisticated debugging techniques
can  be implemented,  particularly  in an  on-line  implementation of
LISP.

		Example of a Useful Functional Argument

	The  function,  mapcar  [x  ;  fn],  is  a  function  of  two
arguments.   fn is a functional  argumet.  x is a  list, (x (sub)1, x
(sub)2...,x (sub)n).   the  value returned  is a  list consisting  of
(fn[x  (sub)1], fn[x  (sub)2],...,fn[x (sub)n]).  mapcar can  thus be
defined as:

	mapcar = λ[x ; fn][null [x] → NIL
			T → cons[fn[car [x]];mapcar[cdr [x];fn]]]]

for example:

	λ[[j] mapcar [j ; function [add1]]][(0,1,2)] = (1,2,3)

or in the new definition of apply:

	evlis [x] = mapcar [x ; function [eval]]
			SYSTEMS ORGANIZATION

	There are  many applications of  data structures  which arise
very  naturally in the domain  of systems programming.   This section
will begin  with  a  very  brief historical  description  of  systems
organization, from the bare machine to multi-processing.
	In  the  early  days of  computers,  operating  systems  were
non-existent.   You would  sign up for  a couple of  hours of machine
time, appear  with your  card deck  or paper  tape,  and operate  the
machine.  Debugging devices consisted of a sharp pointed stick, and a
quick  hand on the console  switches.  This  means of programming was
very satifying to  many of the  programmers, but machine  utilization
left something  to be desired.   Much of  the time the  machine would
sitt idle (stopped) as  you would think  about what to  do next.   As
processing speed and  machine costs increased it became  evident that
this  mode  of operation  had to  go.   The  first  operating systems
consisted of a dull  slow object called  an operator and a  satellite
computer on which an input tape  consisting of many separate jobs was
created.   Each  job  on the  input tape  was swquentially  read into
memory, executed and the output presented to an output tape.  If some
abnormal  behavior  was  detected  in  your program,  you  were  also
presented with an  often uninspiring  octal dump of  the contents  of
memory. Whenever a job required say, a  data tape, the operator would
be notified,  and the machine would wait  until the tape was located,
mounted, and readied.  There was a moderately small  resident monitor
which controlled  the input, output  and perhaps the timing  of jobs.
Gross  utilization of the machine was  increased, however at the cost
of  easy  debugging.    This  mode  of  operation   is  called  batch
processing.
	The CPU  (central processing  unit) still  locks up when  I/O
devices  aren't ready and the  user can physically  halt the machine.
For this  model and  most  of the  future discussion,  it  simplifies
matters to  assume that the  monitor resides  in a separate  core box
from that which contains user programs.

Thus:









The  user programs  are  loaded  into  explicit (hard)  locations  in
memory,  and it is  assumed that  the user has  access to all  of the
addressing space of his core box.
	In  an  attempt  to decrease  the  overhead  on  waiting  for
external actions (I/O  requests or operator intervention) we attach a
reasonably  fast  storage  device  (and  increase  the  size  of  the
monitor).  This storage device is  capable of holding many user jobs.
Whenever  a user (loser)  program requires a service  which cannot be
satisfied immediately,  the  monitor will  swap  the program  out  of
memory onto  this storage device, initiate action  which will tend to
satisfy the request, and bring  another job into core, beginning  its
execution.   This new job  may either  be the next  job on the  input
stream, or  a job which was swapped out and  now is ready to run. The
user still is given  the whole addressing  space, he is still  loaded
into  explicit memory  locations, but  the monitor  must now  be more
cleaver.   It must  be able  to recognize (or  `trap') requests which
would lock up the CPU.  It must be able to make decisions as to which
job to run next.











Clearly  there  are   grossinefficiencies  in  the   present  scheme.
Allowing, or in  fact requiring, that each user have access to all of
memory is too generous.  Assume that our memory size is 32→ words and
assume that we  have 16K jobs which  are ready to run.   We should be
able  to load one job  into locations 0 - (16K-1)  and load the other
job into the  other half of memory.   When one job  requires external
service, we  should be able to  switch the CPU to  begin execution of
the other job provided that we save all information about the current
state of the suspended jog.  The point is  that it takes time to swap
jobs in and out  of core so thaat anything we can do to decrease this
overhead is  a winner.   What  are the  added  requirements for  this
scheme?  Manily we must have some  scheme for keeping the jobs out of
each  other's hair.  This  is usually done by  a hardware addition to
the machine  called the protection  register.   Do typists read  what
they are typing??  No it's a bunch of crap!!!

		[CRAP (1)] ≡ [LISP] sexpr
		N. Meller has a bad attitude.

In this simple scheme the protection register  would be loaded by the
monitor  with the  upper  and lower  bounds on  the  addressing space
accessible to the current job.  Then every memory reference made by a
program is filtered  through the protection register.   Obviously the
instruction  to  load  protection register  should  be  restricted to
execution by the monitor.
	What are  the inefficiencies in  this scheme?   Consider what
happens  when  we have  to  swap a  job  out of  memory.    Since the
addresses  used  by  the  program  are  explicitly  tied   to  memory
locations, we must swap that job  back into exacly the same locations
if  it is  to run correctly.   Consider  two 16K  programs whose only
effect is to execute `jump-self' loops ( L (JRST  L) ). Their initial
load might look like:







If we swap out the top job and try to swap it back into the lower 16K
at some later time, we lose big.








But clearly if the bottom  16K is available we should be  able to use
it.  We want to be able to swap our programs into any available block
of core which is of sufficient size.
	 To  accomplish  this we  add a  new piece  of hardware,  the
relocation register. Now our loader loads all our programs as if they
begin at location, 0.  Thus in the above example:








To get the  appropriate effect when  we execute any program,  we bias
every  memory reference by  actual address assigned  to the program's
location 0.   This  bias is  put in  the relocation  register by  the
monitor before it begins execution of  the program.  With this scheme
we  can run any jobs in any block  of core which is the correct size.
All we  need do  is load  the  appropriate offset  in the  relocation
register.








	Now we can dispense with the two-core box approach.  Just use
one box and bias  every access in a user program by the length of the
monitor plus the usual offset:









The actual harrdware can also be simplified now since the lower bound
on every user's addressing space is always zero.
	Clearly, more refinements  need to be  made.  At  present the
only way  to interrupt a job is if he  terminates,  or calls for some
external action, or  attempts to perform  some illegal or  restricted
instruction.   Any operating system needs  to be able to  monitor the
amount of  CPU time spent on a job.  So we should have a programmable
clock  which can  be  set  by the  monitor  and  which will  send  an
interrupt to the at a  specified time.  Actually other hardware needs
to  be  added  to  our  entourage  if  we  intend  to  do  reasonable
time-sharing.  A  sophisticated   priority  interrupt  system   is  a
necessity.  Since  many of the applications of data structures appear
in time-sharing systems, we will say a bit about the behavior of such
systems.

		   Time-sharing organization

	Though certain ding-dongs  are still publishing  papers about
whether time-sharing  is a useful way o  programming, I feel that the
question has been answered in the affirmative for many years. Period.
	What make  time-sharing viable  is the tremendous  difference
between human reaction time and machine speeds.  In a period of a few
seconds a well  designed t-s  system can satisfy  simple requests  by
many users.   If  a user must  wait a significant  length of  time to
obtain  a  response  to a  simple  command, then  your  system  is in
trouble.   The heart  of a  rapid  response is  a priority  interrupt
system.
	A time-sharing monitor  must service terminals,  mass storage
devices and control the dynamic allocation of its memories.
	Consider the  care and feeding  of a relatively  fast storage
device,  say  a  disk,  and  its  interaction  with the  sending  and
receiving of  characters from user  terminals. Most  disks require  a
sequence of  commands be  issued before an  actual data  transfer can
take  place.  Assume that there are two  commands: a seek to find the
appropriate area on the device, followed by the transfer command.  If
the CPU were tied up from the beginning of the seek to the end of the
transfer, significant  amounts of  CPU time  would be  lost.   If  we
issued the  seek, went  off to  do other  calculations, but were  not
responsive  enough when  the  seek was  completed we  might  miss the
chance to make the transfer due to intervening rotation of  the disk.
What we can do  is put the disk on a  high priority interrupt channel
and  the terminal keyboards on a medium  priority channel.  Issue the
seek, go back  to computation, perhaps  servicing the keyboards;  and
when the disk  is in position we will get  a high priority interrupt,
freezing the  state  of the  computation;  at this  time,  begin  the
transfer of information, dismissing the  interrupt and continuing the
computation.  Thus higher priority requests can interrupt lower ones;
any  lower priority  requests must  be suspended  or saved  until the
higher one is completed.  You might decide to design the  hardware to
allow recursive interrupts  on a particular channel  or might require
completion  before another  request can  be serviced.   (What  do you
think?)
	What about  the  data structures  used in  a complex  system.
Data structures  are used heavily in the  scheduling algorithms.  the
t-s monitor must make decisions about which jobs in the system are to
run.   These decisions are  based on such  simple things as:  the job
isn't  requesting service--dormant; the  job is waiting  for some I/O
device--I/O  wait; or  decisions  must  be based  on  more  difficult
criteria: the  job is ready to  run but is too big  for the currently
available allotment of core;  there is a job  ready which needs  fast
response or has been waiting inordinately long for service.
	In  general a  vast  array  of  information can  be  used  in
deciding which  job to run next.   Usually these decisions take shape
by reqquiring that  the jobs currently in  the system be  partitioned
into  a  finite  set  of  waiting-lines  or  queues.  The  scheduling
algorithm manipulates  these queues as the status of the jobs change.
A queue  is  a  data structure.    Queues  are also  called  first-in
first-out lists (FIFO) or pop-up  lists.  In LISP parlance you append
new queue-elements to the end of  the list and take the elements  off
of the  front of  the  list.   It should  be obvious  where the  name
waiting-line comes from.
	Queues are also used in the buffering schemes of I/O devices.
As we type `LOGIN.....'  to a t-s system, it is usually the case that
the character string first goes into a system buffer and when the CPU
is free,  the command is decoded.   Obviously we want  the monitor to
see  the character  string in the  same order  in which  we typed it.
That is the buffer is acting like a queue.
	A queue can be implemented as simply a list with a pointer to
the front,  and a pointer to the end.   When you add something to the
end, you update one  pointer; wen you take  an element off the  front
you update  the other pointer.   There is  the obvious check  to make
sure  that you can recognize the empty  queue: when the front pointer
meets the end pointer:





As with  stacks, the queue  is usually not  represented as a  list of
argitrary length.  A queue can be represented  as a sequential set of
memory locations, still with two pointers.  What happens when we have
filled the  last cell in  the sequence.  Well,   if some  process has
been removing items from the queue, then the front pointer has moved:




In this case  the cells from  the first cell  in the sequence  to the
current position of  the front pointer are available.  Use `em.  That
is a queue is usually implemented as a sequential circular  list with
two pointers.   In this implementation the tests for  the empty queue
are  slightly more complex, but are still  obvious.  Notice too, that
we must now also test for the full queue.
	In  system applications  it  is  usually  the case  that  one
process is filling the queue and one process is emptying it.  In this
application, a full  queue should simply put  the filling process  to
`sleep' (or suspend it), and when a queue becomes empty, the emptying
process  should  be  suspended.    There  are  some  interesting  and
non-trivial  problems   which   arise   in  connection   which   such
`cooperating processes'.
	There are some interesting data  structure applications which
are connected with  the allocationa dn (?) liberation of storage. The
monitor  must  be  able  to   allocate  storage  to  jobs  as   their
requirements become known  and must also be able to  recover areas of
memory which  are no longer being used.  Similarly, since an integral
part of a large system is a file structure, the  monitor must be able
to handle  the demands of file  maintenance.  These  two problems are
related  but  solutions  for  core  allocation  are  not  necessarily
reasonable ones for file allocation.
			NUMBERS IN LISP

	Inums, Fixnum, Flonums, and Bignums
On most versions of LISP, numbers are stored  as very simple kinds of
atoms:  they do not  need print names,  but since  we should probably
allow fixed and floating point representation, we do  need indicators
for these properties.  Thus:







Notice that each actual number is stored in FWS.  This representation
is a  bit expensive.  On  some machines we can use  a coding trick to
improve representation of some  numbers.  Assume that the  addressing
space of the machine  is 2 (sup)18 and that the usual  size of a LISP
core image is significantly smaller, say, N.  Then all memory address
references greater than N  are illegal (and trapped by  the monitor).
What we  will do is use  these illegal address to encode  some of the
smaller positive and  negative integers, mapping  zero on the  middle
address, the  positive numbers to  lower addresses and  the negatives
onto  the  higher   addresses.    Thus  these  smaller  integers  are
represented by pointers outside of the normal LISP  addressing space.
This  trick can  considerably decrease  the storage  requirements for
jobs  heavily using small  numbers.  (Numbers are  not usually stored
uniquely).











Most  numerically oriented  programs  are  faced  at some  time  with
overflow.  That is, they attempt  to construct a number  which is too
large to  be represented  in one  machine location.    There are  now
several   versions   of   LISP  which   will   automatically   change
representation  when faced  with overflow.   This  new representation
called Bignums, could have the following structure:









The value of Bignum is given by:

 
where α-1 is  the largest number  representable in one  machine word.
The intertranslations  between Inums, Fixnums or Flonums, and Bignums
is done automatically by eval and Co.
		STORAGE STRUCTURES AND EFFICIENCY

	Though it is true that any algorithm can be coded in terms of
manipulations of binary trees, there are many instances in which more
efficient organizations of data exit.
	At the most elementary  level are vectors and arrays.   These
data structures could  certainly be stored in a list structure format
and individual components accessed via car-cdr chains.  However, most
machines  have a  hardware  organization which  can  be exploited  to
increase   accessing   efficiency  over   the   list  representation.
Similarly, strings can  be represented as  lists of characters.   The
string processing operations are expressible as LISP algorithms.  But
again this is usually not the most resonable representation. Even  at
the level of list-structure operations, simple binary trees might not
be the most  expeditious representation for every problem.  Also many
of the algorithms we  have presented in  LISP are overly wasteful  of
computation time.  This section of notes will begin an examination of
alternatives   to  LISP  organization.     There  is   no  best  data
representation, or no best algorithm.  The representations you choose
must match your machine and  the problem domain you are studying.  If
your application is strictly numerical then list-structure is not the
answer; if you wish to manipulate simple linear strings of characters
then list processing is too general.  And there are many applications
of list processing which are sufficiently well-behaved that you don't
need a storage  allocation device as complex as  a garbage collector.
The point  is that if you have seen the list-processing techniques in
a rich environment  such as  LISP and have  seen the applications  to
which  LISP may  be put,  then you  will be  prepared to  apply these
techniques  in  a  meaningful  way.    Many  times  an  (inefficient)
representation in  LISP  is all  that is  needed.   You  get a  clean
representation  with comprehensible algorithms.   Once you've studied
the algorithms, efficiencies might come to mind. At that  time either
recode the problem using some  of the obscene LISP programming tricks
or drop into machine language if very fine control is required.  Once
you have  a  representation it  is  easy to  get  better ones.    For
example,  one you have  a compiler  (which is  proved correct)  it is
easier to describe a smarter one.
		
			Storage Structures

	Bit tables: In the marking phase of a garbage collector it is
necessary to  record the marking of each word.   On many machines the
marking of a word is signified by setting a bit in a bit table or bit
map.  For example:












This  might be  done for  several  reasons.   The  natural choice  of
setting  a mark-  bit  in the  actual word  being  marked may  not be
possible of no  the best strategy: 1)  for words in  FS, there is  no
room if each  word contains exactly two addresses; or  2) the word is
in  FWS and  the  meaning of  the information  stored there  would be
changed;  3) also  the  garbage  collector must  initialize  all  the
mark-bits to  zero before the actual marking  process begins (look at
the g.c. algorithm).  It is faster  on most machines to zero a  whole
table rather than zero single bits in  separate words; and finally 4)
in  garbage collectors for more  complicated data structures, marking
with a bit table becomes a necessity.
	Vectors:  Vectors (or  one  dimensional arrays)  are  usually
stored sequentially in memory.  Simple vectors are usually stored one
element to a  memory location though  this is not  a necessity.   For
example a complex vector is very  naturally stored as pairs of cells;
or if  perhaps you would allow vectors of non-homogeneous data modes,
each element would  have to include type  information.  In any  case,
most languages make some restrictions on the behavior of vectors such
that efficient accessing of elements can be made.  There is a natural
simulation of  a stack as  a (sequential) vector  with access  to the
stack made via a global pointer to the vector.
	Arrays: Arrays are multi-dimensional data  structures.  Since
most  machine memories are linear  devices we must map  arrays onto a
linear representation.   We will  restrict attention fo  the case  of
two-dimensional  arrays.   Most  of the  discussion generalizes  very
naturally.   A very common device is to store the array by rows; that
is,  each  row is stored sequentially,  first, row 1; then  row 2,...
Given this representation there  is a trivial calculation to find the
location of an arbitrary element, A[i;j], if we know the location  of
the first  element, A[1;1] and  the extent of  the dimensions  of the
array.  For an array A[1:M; 1:N]

		loc[A[i;j]] = loc [a[1;1]] + (i-1)*N + (j-1)

In languages like Fortran which require that the size of the array be
known at compiler-timer  the compiler can generate the accessing code
without problem.  Languages, like Algol 60, and some versions of LISP
which allow the size of an  array to be determined at runtime require
a bit more care.  Algol 60, for example requires that you declare the
type (real, boolean,  etc.) of  the array and  specify the number  of
dimensions  in the  array,  but you  can postpone  until  runtime the
designation of the size of each dimension.  To handle this complexity
a dope vector is  introduced. The compiler can determine  the size of
the dope vector, but  not the contents.  The dope vector is filled in
at runtime and  contains information about the  actual extent of  the
array bounds.   Also since  the size of the  array is not  known, the
compiler  cannot   allocate  space  for  the  array  elements.    The
allocation must be  done at runtime.   When the array declaration  is
executed we must  know all the information about the  array.  At that
time we add the  array-bound information to the  dope vector and  add
information telling where  to find the  array elements.   Assume that
the  array elements are stored  by rows.  Look  at the calculation of
the location of element, A[i;j].   For specific execution ofan  array
declaration much  of this information  is constatnt; the  location of
the array  elements, in particular, A[1;1] and the number of columns,
N, is fixed.  Thus we rewrite the calculation as:

		constant part			variable part

		[loc [A[1;1]]-N-1]       +   	(i*N+j)

The constatnt  part is sored  in the  dope vector.   When we wish  to
reference  an element A[i;j] we  need only compute  the variable part
and add it to the constant part.
	The dope vector for A [1:M; 1:N] perhaps might contain












	There is another scheme  for storing arrays which is  used in
some of  the Burroughs machines. Each row  is stored sequentially and
access  to  separate  rows  is   made  through  a  device  called   a
`mother-vector'.   The mother vector is  a vector of pointers  to the
rows.  Thus:










Notice that the accessing computation is very  cheap.  Another effect
is  that all rows  need not  be in memory  at once.   On a  paging or
segmenting machine (we  will talk  about machine organization  later)
this array organization can be helpful.  If an access to a row not in
core  is made, a `page  fault' is raised; the  monitor brings the row
into memory and the computation continues.   The mother-vector scheme
generalizes  nicely  to   multidimensionality  and  can  be  used  in
conjunction with a dope vector.
	Strings: Strings and string processors are an important class
of data  structures and algorithms.  Powerful  string processing is a
necessity  for any  well  developed  compiler-writing  system.    The
organization  and  implementation  of   a  general  string  processor
directly parallels  (you guessed it) LISP.  In fact a subset of LISP,
linear LISP,  is a nice notation for string algorithms.
	A string is a sequence of characters.   A reasonable language
(not PL/1) for string processing should allow the creation of strings
of arbitrary length at runtime; it should allow the generation of new
strings and the  decomposition of existing  strings.  I f  strings of
arbitrary length are  to be created, an organization similar to FS in
LISP can be used with, perhaps, a string garbage collector.   We will
assume this most general case.
	The machine memory will  contain at least a string  space, an
evaluator, a symbol table, and a garbage collector.
	String space is a linear sequence of cells, each of which can
contain exactly  one charcter.   A string  will be  represented as  a
sequence of sequential character cells.  A string variable will be an
entry in  the symbol table; the current value of the variable will be
represented as a pair; character count and a pointer to the beginning
of the character sequence.

Thus:





We must make some decisions about how  we manipulate strings: when we
perform x←y, do we copy the symbol table pair of y into that of x, or
do we make a new string isomorphic to y and point x at it.   It makes
a  difference.    We  will   choose  the  former,  copying  only  the
`descriptor',  that  is,  we  will  share  strings  (and  substrings)
wherever possible. This decision makes the  storage requirements less
expensive, but will make our  life more difficult when we worry about
garbage  collection.   There are  three  primitive functions:  first,
rest,  concat  (read: car,  cdr,   cons).    first [x]  is  the first
character of the string represented by x.  first is undefined for the
empty string. For example:

		first [ABC] is A; first [∧] is undefined

rest[x] is  the string  of characters  which remains  when the  first
character of  the string is deleted.  rest  is also undefined for the
empty string. For example:

		rest [ABC] is BC

concat [x;y] is a function of two arguments.   x is a character; y is
a  string. concat forms  a string  consisting of the  concatenation a
copy of x and a copy of the string, y.  For example:

		concat [A ; BC] is ABC
	
There are three string predicates:
	char [x]:  is x a single character?
	null [x]:  is x the empty string?
	x = y:  are x and y the same character?
For example:

		char [A] is true
		char [AB] is false
		AB = AB is undefined

	Now to implementations:
	first generates a character  count of 1 and a  pointer to the
first character of the parent string.
	rest generates a character count of one less than that of the
parent and a pointer to the second character of the parent string.
	concat is a  bit more  problematic.   We copy x  and copy  y,
generate  a character  count of  the sum  of those  of x  and y,  and
generate a pointer to the character of the copy of x.  The copies are
made in the free string space pointed to by the string space pointer.
The obvious  question of  what to do  when string space  is exhausted
will be postponed  for a moment.   The implementations  of the  three
predicates are easy: we will blur  the distinction between characters
and strings  of length 1.  Thus char  need check the character count.
null says character count is 0.  What about = ?  Obviously characters
are  not  stored   uniquely,  so  we must  make  an  actual character
comparison.
	Now  garbage collection.    In  some  ways a  string  garbage
collector is simpler and in some ways more difficult than a collector
of list-structure.   The  marking phase  is much  simpler: using  the
descriptor in the symbol table, mark  the character string.  Since we
are sharing  substrings, we cannot stop the marking simply because we
have encountered a previously  marked character.  (think  about it!!)
But at least  the marking is not recursive.   However, the collection
phase needs to be  more sophisticated for  string processors.   Since
strings are  stored linearly (or  sequentially), a  fragmented string
space  list  is  of  little  use.    Thus  we  must compact  all  the
referenceable strings into one end of string space, freeing  a linear
block for the new free string space.  Since we are sharing substrings
a  little care  needs  to  be exercised.    When  we move  a  string,
obviously the descriptor of any variable referencing any part of that
parent string must be changed to reflect the new location.  So before
we begin the relocation of strings  we sort the string descriptors on
the  basis of their  pointers into  string space.   We then recognize
each parent string, moving it down into freed  locations and updating
the address  pointers of any  substrings.  We  continue this process.
Eventually all strings will  be compacted down  in string space.  The
free space  pointer will  be set  and the  computation can  continue.
Compacting garbage collectors  can be adapted for use in LISP or more
general types of data structures.  (Think about this)
	List  processing: We  will  first look  at  some LISP  coding
tricks which when used judiciously, can increase efficiency, but when
used in a cavalier manner can result in mystery.  First, LISP does an
awful lot of copying.  Consider:

	append [x;y] = [null [x] →T→cons [car [x]; append [cdr[x];y]]]

This function copies x onto the front of y.   (note: y is not copied)
Or look  at the subst function: it generates  a copy with the correct
substitutions made.   The copying is necessary  in general. It  keeps
unsavory side effects from happening.
	Let's look at append [(A B C) ; (D E F)].  It appears that we
could get the appropriate effect of append by `cdr-ing' down the list
(A B C) until we found the terminator, then replace it with a pointer
to the list (D E F).  Thus:




What's wrong here?  Consider the sequence of statements:

		i ← (A,B,C)

		j ← (D,E,F)

		k ← append [i;j]

Then if append worked  as advertised above, (changing the  cdr of the
last element of i) the following evil would be perpetrated: the value
of  i  has  been  chaged  surreptitiously!!  i  now  has   the  value
(A,B,C,D,E,F).   Language features which  do this  are evil.   It is,
however,  quite useful to be  evil sometimes.   Notice that any value
which was sharing  part of the structure  of i will also  be changed.
This can cause real mystery!! Well the world is good, and append does
not work as above.   The LISP  function which does  work this way  is
called nconc.   I  can be  defined in  terms of  a primitive  obscene
function, rplacd.  There are two primitive obscene functions:

rplaca [x ; y] replace the car of x with y.







rplacd [x; y]:  replace the cdr of x with y.








Thus nconc can be defined as:
nconc [x; y] = prog [[z]
	       [null [x] → return [y]];
		z ← x;
	       a[null [cdr [z]] → rplacd [z ; y] return [x]];
	     	z ←cdr [z];
		go [a] ]
These functions  must be  used with  extreme caution.   They are  not
recommended for amateur hacking.  They are introduced here simpley to
show that  it  is  possible to  improve  on the  efficiency  of  pure
algorithms by resorting to these coding tricks.
Consider:

		x ← (NOTHING CAN GO WRONG)
		rplacd [cdddr [x] ; cddr [x]]
		print [x]

So we can use rplacd to generate circular lists (and to generate wall
paper  by printing  them!!) In  general,  to circularize  a non-empty
list, x, rplacd [last [x]; x] suffices where:

		last [x] = [null [cdr [x]] → x; T → last [cdr [x]]]